package com.nipun.graph.algorithms;

import java.util.ArrayList;
import java.util.List;

import com.nipun.graph.objects.Edge;
import com.nipun.graph.objects.Graph;
import com.nipun.graph.objects.Vertex;


public class ConnectedGraph {

	private Graph g;
	Object[] nodes;
	Object[] edges;
	List[] lists;
	int tokens;
	
	public ConnectedGraph(Graph graph){
		g = graph;
		nodes = g.getVertices();
		edges = g.getEdges();
		lists = new List[nodes.length];
		tokens = nodes.length;
		for(int i=0;i<lists.length;i++){
			lists[i] = new ArrayList();
			lists[i].add(nodes[i]);
		}
	}
	
	public boolean isConnected(){
		boolean result = false;
		for(int i=0; i<edges.length; i++){
			Edge e = (Edge)edges[i];
			int pos1 = whereIs(e.getNode1());
			int pos2 = whereIs(e.getNode2());
			if(pos1 != pos2){
				for(int j=0; j<lists[pos1].size();j++){
					lists[pos2].add(lists[pos1].get(j));
				}
				while(lists[pos1].size()>0){
					lists[pos1].remove(0);
				}
				tokens--;
			}
		}
		if(tokens <= 1){
			result = true;
		}
		return result;
	}
	
	private int whereIs(Vertex v){
		int pos = -1;
		for(int i=0; i<lists.length;i++){
			if(lists[i].contains(v)){
				pos = i;
				break;
			}
		}
		return pos;
	}
}
